package com.tys.algorithm.advanced.code.class23;

public class Code03_NQueens {

    //方法1：
    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return process1(0, record, n);
    }

    // 当前来到i行，一共是0~N-1行
    // 在i行上放皇后，所有列都尝试
    // 必须要保证跟之前所有的皇后不打架
    // 一维数组：int[] record 已经满足条件的数组,索引是行，值是列
    // record[x] = y 表示之前的第x行的皇后，放在了y列上
    // 返回：不关心 i 以上发生了什么，i.... 后续有多少合法的方法数
    public static int process1(int i, int[] record, int n) {
        //填完了
        if (i == n) {
            //发现一种方法
            return 1;
        }
        int res = 0;
        // i行的皇后，放哪一列呢？
        // 放j列，挨个试
        for (int j = 0; j < n; j++) {
            //是否打架
            if (isValid(record, i, j)) {
                //不打架
                record[i] = j;
                //向下统计
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }

    //是否打架
    public static boolean isValid(int[] record, int i, int j) {
        // 检查范围：0..i-1
        for (int k = 0; k < i; k++) {
            if (j == record[k] || //共列
                    Math.abs(record[k] - j) == Math.abs(i - k)) { //共斜线
                return false; //打架
            }
        }
        //不打架
        return true;
    }

    // 方法2：使用位运算，优化常数时间，
    // 请不要超过32皇后问题：超过整数范围算不了
    public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        // 如果你是13皇后问题，limit 最右13个1，其他都是0
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }

    // 7皇后问题
    // limit固定不变 : 0....0 1 1 1 1 1 1 1
    // 之前皇后的列影响：colLim 状态
    // 之前皇后的左下对角线影响：leftDiaLim 状态
    // 之前皇后的右下对角线影响：rightDiaLim 状态
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        //发现1种方法
        if (colLim == limit) {
            return 1;
        }
        // pos中所有是1的位置，是你可以去尝试皇后的位置
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        //最右侧的1
        int mostRightOne = 0;
        //无效返回0
        int res = 0;
        //尝试所有的1
        while (pos != 0) {
            //得到最右侧的1，1位置可以放皇后
            mostRightOne = pos & (~pos + 1);
            //下一个皇后
            pos = pos - mostRightOne;
            res += process2(limit,
                    colLim | mostRightOne, //得到新的列限制
                    (leftDiaLim | mostRightOne) << 1,//得到新的左对角线限制
                    (rightDiaLim | mostRightOne) >>> 1);//得到新的右对角线限制
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 15;

        long start = System.currentTimeMillis();
        System.out.println(num2(n));
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        System.out.println(num1(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

    }
}
